#ifndef CHAIN_H_
#define CHAIN_H_

#include <iostream>
#include <sstream>
#include <string>
#include "myExceptions.h"

using namespace std;

template<class T>
class linearList 
{
   public:
      virtual ~linearList() {};
      virtual bool is_empty() const = 0;
                  // return true iff list is empty
      virtual int size() const = 0;
                  // return number of elements in list
      virtual T& get(int index) const = 0;
                  // return element whose index is theIndex
      virtual int index(const T& element) const = 0;
                  // return index of first occurence of theElement
      virtual void erase(int index) = 0;
                  // remove the element whose index is theIndex
      virtual void insert(int index, const T& element) = 0;
	  virtual bool remove(const T &element) = 0;
	 
	  virtual void push_back(const T& element) = 0;
	  virtual void pop_back() = 0;
                  // insert theElement so that its index is theIndex
      virtual void out_put(ostream& os) const = 0;
                  // insert list into stream out
};


template <class T>
struct chainNode 
{
   // data members
   T _element;
   chainNode<T> *_next;

   // methods
   chainNode() {}
   chainNode(const T& element)
      { _element = element; }
   chainNode(const T& element, chainNode<T>* next)
      { _element = element;
        _next = next; }
};

template <class T>
class chain: public linearList<T>
{
	public:
	    // constructor, copy constructor and destructor
	    chain(int initialCapacity = 10);
		chain(const chain<T>& );
		~chain();
		
		// ADT methods
		bool is_empty() const { return _listSize == 0; }
		int size()      const { return _listSize; }
		T& get(int index) const;
		int index(const T &element) const;
		void erase(int index);
		void insert(int index, const T& element);
		bool remove(const T &element);		 
		
		void push_front(const T& element);
		void pop_front();
		
		void push_back(const T& element);
		void pop_back();
		void clear();
		void out_put(ostream &os) const;
		void merge(const chain<T>&);
		
		// iterator to strat and end of list
		class iterator;
		iterator begin() { return iterator(_firstNode); }
		iterator end()   { return iterator(NULL); }
		
		// iterator for chain 
		class iterator
		{
			public:
			    typedef forward_iterator_tag iterator_category;
				typedef T value_type;
				typedef ptrdiff_t difference_type;
				typedef T* pointer;
				typedef T& reference;
				
				// constructor 
				iterator(chainNode<T>* node = NULL)
				        { _node = node; }
				T& operator*()  const { return _node->_element; }
				T* operator->() const { return &_node->_element; }
				
				// increment
				iterator& operator++()      // preincrement
				        { _node = _node->_next; }
				iterator operator++(int)
				        { iterator old = *this;
						  _node = _node->_next;
						  return old;}
				
				// equality testing
				bool operator!= (const iterator right) const
				        { return _node != right._node; }
				bool operator== (const iterator right) const
				        { return _node == right._node; }
			
			protected:
			    chainNode<T>* _node;
		};
		
	protected:	    
        void check_index(int index) const;
		
        chainNode<T>* _firstNode;
        int _listSize;		
};

template<class T>
chain<T>::chain(int initialCapacity)
{
	if (initialCapacity < 1) {
		ostringstream s;
		s << "Initial capacity = " << initialCapacity
		  << "Must be > 0";
		throw illegalParameterValue(s.str());
	}
	_firstNode = NULL;
	_listSize = 0;
}

template<class T>
chain<T>::chain(const chain<T>& list)
{
	_listSize = list._listSize;
	
	if (_listSize == 0) {
		_firstNode = 0;
		return;
	}
	
	// non - empty list
	chainNode<T>* sourceNode = list._firstNode;
	_firstNode = new chainNode<T>(sourceNode->_element);
	
	sourceNode = sourceNode->_next;
	chainNode<T>* targetNode = _firstNode;
	
	while(sourceNode != NULL) {
		targetNode->_next = new chainNode<T>(sourceNode->_element);
		targetNode = targetNode->_next;
		sourceNode = sourceNode->_next;
	}
	targetNode->_next = NULL; // end the chain
}

template<class T>
chain<T>::~chain()
{
	clear();
}

template<class T>
inline void chain<T>::check_index(int index) const
{
	if (index < 0 || index >= _listSize) {
		ostringstream s;
		s << "index = " << index << " size = "
          << _listSize;
        
		throw illegalIndex(s.str());
	}
}

template<class T>
inline T& chain<T>::
get(int index) const
{
	check_index(index);
	
	chainNode<T>* currentNode = _firstNode;
	
	for (int i = 0; i < index; i++)
        currentNode = currentNode->_next;
    
    return currentNode->_element;	
}

template<class T>
inline int chain<T>::
index(const T& element) const
{
	chainNode<T>* currentNode = _firstNode;
	int index = 0;
	
	while(currentNode != NULL && currentNode->_element != element) {
		currentNode = currentNode->_next;
		index ++;
	}
	
	if (currentNode == NULL)
		return -1;
	else 
		return index;
}

template<class T>
inline void chain<T>::
erase(int index)
{
	check_index(index);
	
	chainNode<T>* deleteNode;
	if (index == 0) {
		deleteNode = _firstNode; 
		_firstNode = _firstNode->_next;
	}
	else {
		chainNode<T>* p = _firstNode;
		for (int i = 0; i < index - 1; i ++) {
			p = p->_next;
		}
		deleteNode = p->_next;
		p->_next = deleteNode->_next;
	}
	_listSize --;
	delete deleteNode;
}

template<class T>
inline void chain<T>::
insert(int index, const T& element)
{
	if (index < 0 || index > _listSize) {
		ostringstream s;
		s << "index = " << index << " size = " << _listSize;
		throw illegalIndex(s.str());
	}
	
	if (index == 0)
		_firstNode = new chainNode<T>(element, _firstNode);
	else {
		chainNode<T>* p = _firstNode;
		for (int i = 0; i < index - 1; i++)
			p = p->_next;
		p->_next = new chainNode<T>(element, p->_next);
	}
	_listSize++;
}

template<class T>
inline void chain<T>::push_back(const T &element)
{
	int index = _listSize;
	insert(index, element);
}

template<class T>
inline void chain<T>::
pop_back()
{
	int index = _listSize - 1;
	erase(index);
}


template<class T>
inline void chain<T>::push_front(const T &element)
{
	insert(0, element);
}

template<class T>
inline void chain<T>::
pop_front()
{
	erase(0);
}

template<class T>
inline bool chain<T>::
remove(const T &element)
{
	bool ok = true;
	chainNode<T> *currentNode = _firstNode;
	
	int index = 0;
	while (index < _listSize && currentNode->_element != element) {
		currentNode = currentNode->_next;
		index ++;
	}
			
	if (index == _listSize)
		return (ok = false);
	else {
		erase(index);
		return (ok = true);
	}
}

template<class T>
inline void chain<T>::
clear()
{
	chainNode<T> *nextNode;
	
	while (_firstNode != NULL) {
		nextNode = _firstNode->_next;
		delete _firstNode;
		_firstNode = nextNode;
	}
	_listSize = 0;
}

template<class T>
inline void chain<T>::
merge(const chain<T> &y)
{	
    chainNode<T>* tagNode = y._firstNode;
	
	while (tagNode != NULL) {
		push_back(tagNode->_element);
		tagNode = tagNode->_next;
	}
}

template<class T>
inline void chain<T>::
out_put(ostream& os) const
{// Put the list into the stream out.
   for (chainNode<T>* currentNode = _firstNode;
                      currentNode != NULL;
                      currentNode = currentNode->_next)
      os << currentNode->_element << "  ";
}


// overload <<
template <class T>
inline ostream& operator<<(ostream& os, const chain<T>& x)
   {x.out_put(os); return os;}

#endif